Serveur d'exploration sur la visibilité du Havre

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Un algorithme de branch-and-price-and-cut pour la planification durable de rotations agricoles

Identifieur interne : 000273 ( France/Analysis ); précédent : 000272; suivant : 000274

Un algorithme de branch-and-price-and-cut pour la planification durable de rotations agricoles

Auteurs : Laurent Alfandari [France] ; Agnès Plateau [France] ; Xavier Schepler [France]

Source :

RBID : Hal:hal-00946289

Descripteurs français

Abstract

Les problèmes de contruction de rotations agricoles connaissent un essor important dans la littérature depuis les cinq dernières années, notamment dans un objectif de développement durable. Nous nous intéressons ici à un problème spécifique de minimisation de l'espace agricole requis pour couvrir des demandes saisonnières en diverses cultures, dans un contexte de tension sur les ressources foncières. Une rotation alterne des périodes de culture et de jachère sur un horizon de temps et sur une parcelle de taille donnée, avec des rendements croissants en fonction de la durée de la dernière jachère et décroissants en fonction de la durée de culture. Nous montrons que le problème est NP-difficile au sens fort par réduction avec le problème de couverture d'ensemble. Nous introduisons une formulation compacte du problème de type flot multi-commodités avec variables arcs, sur la base d'un graphe de séquences multi-états associé à chaque parcelle. Nous proposons ensuite une formulation étendue de type Covering Integer Programming, issue d'une décomposition Dantzig-Wolfe. La relaxation continue de cette formulation étendue est résolue par génération de colonnes. Un sous-problème de pricing polynomial est associé à chaque parcelle, résolu par programmation dynamique. Cette résolution par génération de colonnes du problème maître est intégrée à un algorithme de branch-and-price-and-cut, avec règles de branchement et plans coupants adaptés à la structure du problème. L'originalité de cette communication réside dans la définition du problème et l'application de cette technique de branch-and-price-and-cut (BPC) alors qu'à notre connaissance, ni branch-and-price ni branch-and-cut n'avaient été appliqués auparavant à un problème de construction de rotations agricoles, au-delà de quelques papiers existants utilisant la génération de colonnes. La méthode proposée fournit d'excellents résultats sur des instances faisant varier le nombre de cultures, l'horizon de temps et la taille des parcelles. Pour les petites instances le BPC fournit la meilleure solution pour la totalité des 20 instances, contre 17/20 pour la résolution directe de la formulation compacte, avec des temps réduits en cas d'égalité. Pour les instances plus difficiles avec un temps limite de 3600s, le BPC fournit la meilleure solution pour 23 des 30 instances, contre 7/30 pour la formulation compacte. Ce résultat est obtenu malgré l'égalité de la borne LP entre les deux formulations. Enfin, un apport du papier est de confirmer un résultat théorique que plus le morcellement des parcelles est important, plus l'espace requis pour couvrir les demandes à l'optimum est réduit, la taille des parcelles étant donc un paramètre critique non seulement pour la résolution du problème mais aussi pour l'objectif de développement durable.


Url:


Affiliations:


Links toward previous steps (curation, corpus...)


Links to Exploration step

Hal:hal-00946289

Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="fr">Un algorithme de branch-and-price-and-cut pour la planification durable de rotations agricoles</title>
<author>
<name sortKey="Alfandari, Laurent" sort="Alfandari, Laurent" uniqKey="Alfandari L" first="Laurent" last="Alfandari">Laurent Alfandari</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-141275" status="VALID">
<orgName>Information Systems, Decision Sciences and Statistics Department</orgName>
<orgName type="acronym">SID</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301020" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-301020" type="direct">
<org type="institution" xml:id="struct-301020" status="VALID">
<orgName>Essec Business School</orgName>
<desc>
<address>
<addrLine>1, avenue Bernard HirschCS 50105 Cergy95021 Cergy Pontoise CedexFranceTél : +33 (0)1 34 43 30 00Fax : +33 (0)1 34 43 30 01</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.essec.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Plateau, Agnes" sort="Plateau, Agnes" uniqKey="Plateau A" first="Agnès" last="Plateau">Agnès Plateau</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-207447" status="VALID">
<orgName>Centre d'Etude et De Recherche en Informatique et Communications</orgName>
<orgName type="acronym">CEDRIC</orgName>
<desc>
<address>
<addrLine>CNAM-CEDRIC 292 Rue St Martin FR-75141 Paris Cedex 03</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://cedric.cnam.fr</ref>
</desc>
<listRelation>
<relation active="#struct-303630" type="direct"></relation>
<relation active="#struct-179741" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-303630" type="direct">
<org type="institution" xml:id="struct-303630" status="VALID">
<orgName>Conservatoire National des Arts et Métiers [CNAM] : EA4629</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-179741" type="direct">
<org type="institution" xml:id="struct-179741" status="VALID">
<orgName>Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise</orgName>
<orgName type="acronym">ENSIIE</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.ensiie.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Schepler, Xavier" sort="Schepler, Xavier" uniqKey="Schepler X" first="Xavier" last="Schepler">Xavier Schepler</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-400226" status="INCOMING">
<orgName>LITIS, Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-23832" type="direct"></relation>
<relation active="#struct-300317" type="indirect"></relation>
<relation name="EA4108" active="#struct-300318" type="indirect"></relation>
<relation active="#struct-301288" type="indirect"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-23832" type="direct">
<org type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300317" type="indirect">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="indirect">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="indirect">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName>
<settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00946289</idno>
<idno type="halId">hal-00946289</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946289</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00946289</idno>
<date when="2014-02-26">2014-02-26</date>
<idno type="wicri:Area/Hal/Corpus">000766</idno>
<idno type="wicri:Area/Hal/Curation">000766</idno>
<idno type="wicri:Area/Hal/Checkpoint">000161</idno>
<idno type="wicri:Area/Main/Merge">000286</idno>
<idno type="wicri:Area/Main/Curation">000285</idno>
<idno type="wicri:Area/Main/Exploration">000285</idno>
<idno type="wicri:Area/France/Extraction">000273</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="fr">Un algorithme de branch-and-price-and-cut pour la planification durable de rotations agricoles</title>
<author>
<name sortKey="Alfandari, Laurent" sort="Alfandari, Laurent" uniqKey="Alfandari L" first="Laurent" last="Alfandari">Laurent Alfandari</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-141275" status="VALID">
<orgName>Information Systems, Decision Sciences and Statistics Department</orgName>
<orgName type="acronym">SID</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301020" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-301020" type="direct">
<org type="institution" xml:id="struct-301020" status="VALID">
<orgName>Essec Business School</orgName>
<desc>
<address>
<addrLine>1, avenue Bernard HirschCS 50105 Cergy95021 Cergy Pontoise CedexFranceTél : +33 (0)1 34 43 30 00Fax : +33 (0)1 34 43 30 01</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.essec.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Plateau, Agnes" sort="Plateau, Agnes" uniqKey="Plateau A" first="Agnès" last="Plateau">Agnès Plateau</name>
<affiliation wicri:level="1">
<hal:affiliation type="laboratory" xml:id="struct-207447" status="VALID">
<orgName>Centre d'Etude et De Recherche en Informatique et Communications</orgName>
<orgName type="acronym">CEDRIC</orgName>
<desc>
<address>
<addrLine>CNAM-CEDRIC 292 Rue St Martin FR-75141 Paris Cedex 03</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://cedric.cnam.fr</ref>
</desc>
<listRelation>
<relation active="#struct-303630" type="direct"></relation>
<relation active="#struct-179741" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-303630" type="direct">
<org type="institution" xml:id="struct-303630" status="VALID">
<orgName>Conservatoire National des Arts et Métiers [CNAM] : EA4629</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-179741" type="direct">
<org type="institution" xml:id="struct-179741" status="VALID">
<orgName>Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise</orgName>
<orgName type="acronym">ENSIIE</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
<ref type="url">http://www.ensiie.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author>
<name sortKey="Schepler, Xavier" sort="Schepler, Xavier" uniqKey="Schepler X" first="Xavier" last="Schepler">Xavier Schepler</name>
<affiliation wicri:level="1">
<hal:affiliation type="researchteam" xml:id="struct-400226" status="INCOMING">
<orgName>LITIS, Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-23832" type="direct"></relation>
<relation active="#struct-300317" type="indirect"></relation>
<relation name="EA4108" active="#struct-300318" type="indirect"></relation>
<relation active="#struct-301288" type="indirect"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-23832" type="direct">
<org type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300317" type="indirect">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="indirect">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="indirect">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName>
<settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
<placeName>
<settlement type="city">Rouen</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="mix" xml:lang="fr">
<term>branch and price and</term>
<term>cut</term>
<term>décomposition</term>
<term>formulations étendues</term>
<term>graphes</term>
<term>génération de colonnes</term>
<term>programmation dynamiques</term>
<term>rotations agricoles</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="fr">

Les problèmes de contruction de rotations agricoles connaissent un essor important dans la littérature depuis les cinq dernières années, notamment dans un objectif de développement durable. Nous nous intéressons ici à un problème spécifique de minimisation de l'espace agricole requis pour couvrir des demandes saisonnières en diverses cultures, dans un contexte de tension sur les ressources foncières. Une rotation alterne des périodes de culture et de jachère sur un horizon de temps et sur une parcelle de taille donnée, avec des rendements croissants en fonction de la durée de la dernière jachère et décroissants en fonction de la durée de culture. Nous montrons que le problème est NP-difficile au sens fort par réduction avec le problème de couverture d'ensemble. Nous introduisons une formulation compacte du problème de type flot multi-commodités avec variables arcs, sur la base d'un graphe de séquences multi-états associé à chaque parcelle. Nous proposons ensuite une formulation étendue de type Covering Integer Programming, issue d'une décomposition Dantzig-Wolfe. La relaxation continue de cette formulation étendue est résolue par génération de colonnes. Un sous-problème de pricing polynomial est associé à chaque parcelle, résolu par programmation dynamique. Cette résolution par génération de colonnes du problème maître est intégrée à un algorithme de branch-and-price-and-cut, avec règles de branchement et plans coupants adaptés à la structure du problème. L'originalité de cette communication réside dans la définition du problème et l'application de cette technique de branch-and-price-and-cut (BPC) alors qu'à notre connaissance, ni branch-and-price ni branch-and-cut n'avaient été appliqués auparavant à un problème de construction de rotations agricoles, au-delà de quelques papiers existants utilisant la génération de colonnes. La méthode proposée fournit d'excellents résultats sur des instances faisant varier le nombre de cultures, l'horizon de temps et la taille des parcelles. Pour les petites instances le BPC fournit la meilleure solution pour la totalité des 20 instances, contre 17/20 pour la résolution directe de la formulation compacte, avec des temps réduits en cas d'égalité. Pour les instances plus difficiles avec un temps limite de 3600s, le BPC fournit la meilleure solution pour 23 des 30 instances, contre 7/30 pour la formulation compacte. Ce résultat est obtenu malgré l'égalité de la borne LP entre les deux formulations. Enfin, un apport du papier est de confirmer un résultat théorique que plus le morcellement des parcelles est important, plus l'espace requis pour couvrir les demandes à l'optimum est réduit, la taille des parcelles étant donc un paramètre critique non seulement pour la résolution du problème mais aussi pour l'objectif de développement durable.

</div>
</front>
</TEI>
<affiliations>
<list>
<country>
<li>France</li>
</country>
<region>
<li>Haute-Normandie</li>
<li>Région Normandie</li>
</region>
<settlement>
<li>Le Havre</li>
<li>Rouen</li>
</settlement>
<orgName>
<li>Université de Rouen</li>
<li>Université du Havre</li>
</orgName>
</list>
<tree>
<country name="France">
<noRegion>
<name sortKey="Alfandari, Laurent" sort="Alfandari, Laurent" uniqKey="Alfandari L" first="Laurent" last="Alfandari">Laurent Alfandari</name>
</noRegion>
<name sortKey="Plateau, Agnes" sort="Plateau, Agnes" uniqKey="Plateau A" first="Agnès" last="Plateau">Agnès Plateau</name>
<name sortKey="Schepler, Xavier" sort="Schepler, Xavier" uniqKey="Schepler X" first="Xavier" last="Schepler">Xavier Schepler</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000273 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000273 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/France
   |area=    LeHavreV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00946289
   |texte=   Un algorithme de branch-and-price-and-cut pour la planification durable de rotations agricoles
}}

Wicri

This area was generated with Dilib version V0.6.25.
Data generation: Sat Dec 3 14:37:02 2016. Site generation: Tue Mar 5 08:25:07 2024